/*
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null
数据 保证 整个链式结构中不存在环

函数返回结果后，链表必须 保持其原始结构
设计一个时间复杂度 O(n) 、仅用 O(1) 内存的解决方案
*/

#include "common.h"

/*
解题思路：

如果有相交的结点D的话,每条链的头结点先走完自己的链表长度,然后回头走另外的一条链表,那么两结点
一定为相交于D点,因为这时每个头结点走的距离是一样的,都是 AD + BD + DC,而他们每次又都是前进1,
所以距离相同,速度又相同,固然一定会在相同的时间走到相同的结点上,即D点

如果不相交，各自走完一遍两个链表，最终汇集在 NULL
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode *p, *q;
    p = headA;
    q = headB;
    while(p != q){
       if(p==NULL)
            p=headB;
       else
            p=p->next;
       if(q==NULL)
            q=headA;
       else
            q=q->next;
    }
    return p;
}


// struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//     if (headA == NULL || headB == NULL) {
//         return NULL;
//     }
//     struct ListNode *pA = headA, *pB = headB;
//     while (pA != pB) {
//         pA = pA == NULL ? headB : pA->next;
//         pB = pB == NULL ? headA : pB->next;
//     }
//     return pA;
// }
